/*
题目链接：https://leetcode.cn/problems/minimize-the-maximum-difference-of-pairs/description/
题目：2616.最小化数对的最大差值
提交时间：2024.9.15
二分，最小化
*/

//分析本题得：①用二分，其中if判断的条件中的mid为假设的“最大值最小”，判断由它计算得到的下标对数与p的大小
//②二分则l为0，最大r为排好序后的最后减最前值

class Solution {
public:
    vector<int>n;
    int P;
    int minimizeMax(vector<int>& nums, int p) {
        sort(nums.begin(),nums.end());   //下标与题目要找的最大值最小无关，则应用二分前进行排序
        for(int i=0;i<nums.size();i++) n.push_back(nums[i]);
        P=p;
        int l=0,r=nums[nums.size()-1]-nums[0];        //注意时初始值为0，最大为排序后的后减前
        while(l<r){
            int mid=l+(r-l)/2;
            if(check(mid)) r=mid;
            else l=mid+1;
        }
        return l;
    }
    int check(int x){
        int i=0;   //表示下标
        int pp=0;   //统计满足把mid视作最大值最小时计算得到的符合要求的下标对数量
        while(i<n.size()-1){    //注意：要-1，防止下面的i+1时越界
        if(n[i+1]-n[i]<=x) {pp++;i+=2;} 
        else i+=1;
        }
        return pp>=P;
    }
};